package com.leecode.xiehf.page_01;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
 * <p>
 * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0030 {

    public static void main(String[] args) {
        Solution_0030 solution = new Solution_0030();
        //   s = "wordgoodgoodgoodbestword",
        //  words = ["word","good","best","word"]
        List<Integer> result = solution.findSubstring(
//                "wordgoodgoodgoodbestword"
//                , new String[]{"word", "good", "best", "good"});
                "ababab"
                , new String[]{"a", "b"});
//                "barfoothefoobarman"
//                , new String[]{"foo", "bar"});
        System.out.println(result);
    }

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return list;
        }
        HashMap<String, Integer> map = new HashMap<>();
        int wordLen = words[0].length();
        int length = words.length;
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        // 把长字符串切成等分的长度，对每个等分的长度进行遍历 减少遍历次数
        for (int i = 0; i < wordLen; i++) {
            int left = i, right = i, count = 0;
            HashMap<String, Integer> hashMap = new HashMap<>();
            while (right + wordLen <= s.length()) {
                String sub = s.substring(right, right + wordLen);
                right += wordLen;
                if (!map.containsKey(sub)) {
                    count = 0;
                    left = right;
                    hashMap.clear();
                } else {
                    // 循环
                    hashMap.put(sub, hashMap.getOrDefault(sub, 0) + 1);
                    // 包含的条数
                    count++;
                    // 包含的条数减掉一部分 (left - right之间的都在map里面，并且没有一个的数量超过map的那么就说明这两个map的元素是一样的)
                    while (hashMap.getOrDefault(sub, 0) > map.getOrDefault(sub, 0)) {
                        String str = s.substring(left, left + wordLen);
                        count--;
                        hashMap.put(str, hashMap.getOrDefault(str, 0) - 1);
                        left += wordLen;
                    }
                    if (count == length) {
                        // 当hashmap的数量恰好等于数组长度就说明不按顺序匹配成功了
                        list.add(left);
                    }
                }
            }
        }
        return list;
    }

    /**
     * 自己实现的
     *
     * @param s
     * @param words
     * @return
     */
    public List<Integer> findSubstring1(String s, String[] words) {
        List<Integer> list = new ArrayList<>();

        int len = words.length;
        if (len == 0) {
            return list;
        }
        int length = words[0].length();
        int m = s.length();
        int n = len * length;
        if (m < n) {
            return list;
        }
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            Integer value = map.get(word);
            map.put(word, value == null ? 1 : value + 1);
        }

        for (int i = 0; i <= m - n; i++) {
            Map<String, Integer> hashMap = new HashMap<>(map);
            for (int j = 0; j < len; j++) {
                String word = s.substring(i + j * length, i + (j + 1) * length);
                if (!hashMap.containsKey(word)) {
                    break;
                }
                Integer count = hashMap.get(word);
                if (count == 1) {
                    hashMap.remove(word);
                } else {
                    hashMap.put(word, count - 1);
                }
            }
            if (hashMap.isEmpty()) {
                list.add(i);
            }
        }
        return list;
    }
}

